1. Field of the Invention
This invention relates to reductions of array variables, and particularly to a method for solving a general reduction problem, which is generalized as a divide-and-conquer problem for solving a problem on an instance of size n, by dividing the instance into two or more smaller instances.
2. Description of Background
Most compilers are capable of recognizing simple reductions such as the accumulation into the variable “SUM” 10 in FIG. 1. Reductions of array variables are also common in scientific codes and are a potential source of significant improvements in parallelization results. In general, a reduction can be expressed in the form of R={r,f,d}, where r can be a scalar variable, an array, or a compound expression. The symbol,  represents an associative reduction operator, ƒ is a function of reduction execution, and d is a domain for reduction operation. Taking the code segment 10 in FIG. 1 as an example, r is a scalar variable, i.e., SUM. is +, ƒ is an identity function, and d is the data area pointed by A ranging from A[1,1] to A[N,M].
Handling such kind of scalar reduction in FIG. 1 is straightforward. There are a number of solutions implemented or proposed. For example, a conventional method is to use a critical section to enable parallel execution of the loop. Another approach is to compute a partial reduction result of each processor and then merge the results to get the overall result. However, for a reduction that involves complicated structures, such as a conditional branch, the identification and implementation is difficult.
For instance, an example code segment 12 in FIG. 2 is considered, which is used to calculate a global maximum and indexes associated with the maximum value. The loop in FIG. 2 cannot be parallelized due to the loop carried dependences on Max_value, Max_index_i and Max_index_j. Another example of a code segment 14 is shown in FIG. 3, which is used to detect the number of array elements whose value is equal to that of variable val. Code segment 12 in FIG. 2 and code segment 14 in FIG. 3 illustrate the difficulty in identifying and implementing a general reduction.
Considering the limitations of the aforementioned methods, it is clear that there is a need for an efficient method for solving a general reduction problem, which is generalized as a divide-and-conquer problem for solving a problem on an instance of size n, by dividing the instance into two or more smaller instances.